home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / language / ici / ici.cpi / set.c < prev    next >
C/C++ Source or Header  |  1994-10-27  |  6KB  |  309 lines
  1. #include "object.h"
  2. #include "set.h"
  3. #include "op.h"
  4. #include "int.h"
  5. #include "buf.h"
  6. #include "null.h"
  7.  
  8. /*
  9.  * Find the set slot which does, or should, contain the key k.
  10.  */
  11. object_t **
  12. find_set_slot(s, k)
  13. register set_t        *s;
  14. register object_t    *k;
  15. {
  16.     register object_t    **e;
  17.  
  18.     e = &s->s_slots[(unsigned long)k % s->s_nslots];
  19.     while (*e != NULL)
  20.     {
  21.     if (*e == k)
  22.         return e;
  23.     if (--e < s->s_slots)
  24.         e = s->s_slots + s->s_nslots - 1;
  25.     }
  26.     return e;
  27. }
  28.  
  29. STATIC long
  30. mark_set(s)
  31. register set_t    *s;
  32. {
  33.     register object_t    **e;
  34.     long        mem;
  35.  
  36.     objof(s)->o_flags |= O_MARK;
  37.     mem = sizeof(set_t) + s->s_nslots * sizeof(object_t *);
  38.     if (s->s_nels == 0)
  39.     return mem;
  40.     for (e = &s->s_slots[s->s_nslots - 1]; e >= s->s_slots; --e)
  41.     {
  42.     if (*e != NULL)
  43.         mem += mark(*e);
  44.     }
  45.     return mem;
  46. }
  47.  
  48. STATIC void
  49. free_set(s)
  50. register set_t    *s;
  51. {
  52.     if (s->s_slots != NULL)
  53.     zfree((char *)s->s_slots);
  54.     zfree((char *)s);
  55. }
  56.  
  57. set_t *
  58. new_set()
  59. {
  60.     register set_t    *s;
  61.  
  62.     /*
  63.      * NB: there is a copy of this sequence in copy_set.
  64.      */
  65.     if ((s = talloc(set_t)) == NULL)
  66.     return NULL;
  67.     objof(s)->o_type = &set_type;
  68.     objof(s)->o_tcode = TC_SET;
  69.     objof(s)->o_flags = 0;
  70.     objof(s)->o_nrefs = 1;
  71.     rego(s);
  72.     s->s_nels = 0;
  73.     s->s_nslots = FEW_OBJS;
  74.     /*
  75.      * Note the FEW_OBJS below is choosen to correspond with the smaller of
  76.      * the special memory lists.
  77.      */
  78.     if ((s->s_slots = (object_t **)zalloc(FEW_OBJS*sizeof(object_t *))) == NULL)
  79.     return NULL;
  80.     memset(s->s_slots, 0, FEW_OBJS * sizeof(object_t *));
  81.     return s;
  82. }
  83.  
  84. STATIC int
  85. cmp_set(s1, s2)
  86. set_t    *s1;
  87. set_t    *s2;
  88. {
  89.     register int    i;
  90.     register object_t    **e;
  91.  
  92.     if (s1 == s2)
  93.     return 0;
  94.     if (s1->s_nels != s2->s_nels)
  95.     return 1;
  96.     e = s1->s_slots;
  97.     i = s1->s_nslots;
  98.     while (--i >= 0)
  99.     {
  100.     if (*e != NULL && *find_set_slot(s2, *e) == NULL)
  101.         return 1;
  102.     ++e;
  103.     }
  104.     return 0;
  105. }
  106.  
  107. STATIC long
  108. hash_set(s)
  109. set_t    *s;
  110. {
  111.     return s->s_nels;
  112. }
  113.  
  114. STATIC object_t *
  115. copy_set(s)
  116. register set_t    *s;
  117. {
  118.     register set_t    *ns;
  119.  
  120.     if ((ns = talloc(set_t)) == NULL)
  121.     return NULL;
  122.     objof(ns)->o_type = &set_type;
  123.     objof(ns)->o_tcode = TC_SET;
  124.     objof(ns)->o_flags = 0;
  125.     objof(ns)->o_nrefs = 1;
  126.     rego(ns);
  127.     ns->s_nels = 0;
  128.     ns->s_nslots = 0;
  129.     if ((ns->s_slots = (object_t **)zalloc(s->s_nslots * sizeof(object_t *))) == NULL)
  130.     goto fail;
  131.     memcpy((char *)ns->s_slots, (char *)s->s_slots, s->s_nslots*sizeof(object_t *));
  132.     ns->s_nels = s->s_nels;
  133.     ns->s_nslots = s->s_nslots;
  134.     return objof(ns);
  135.  
  136. fail:
  137.     loose(ns);
  138.     return NULL;
  139. }
  140.  
  141. /*
  142.  * Grow the set s so that it has twice as many slots.
  143.  */
  144. STATIC int
  145. grow_set(s)
  146. register set_t    *s;
  147. {
  148.     register object_t    **e;
  149.     register object_t    **oldslots;
  150.     register int    i;
  151.  
  152.     i = (s->s_nslots * 2 + 1) * sizeof(object_t *);
  153.     if ((e = (object_t **)zalloc(i)) == NULL)
  154.     return 1;
  155.     memset((char *)e, 0, i);
  156.     oldslots = s->s_slots;
  157.     s->s_slots = e;
  158.     i = s->s_nslots;
  159.     s->s_nslots = s->s_nslots * 2 + 1;
  160.     while (--i >= 0)
  161.     {
  162.     if (oldslots[i] != NULL)
  163.         *find_set_slot(s, oldslots[i]) = oldslots[i];
  164.     }
  165.     zfree((char *)oldslots);
  166.     return 0;
  167. }
  168.  
  169. /*
  170.  * Remove the key from the structure.
  171.  */
  172. int
  173. unassign_set(s, k)
  174. register set_t    *s;
  175. object_t    *k;
  176. {
  177.     register object_t    **sl;
  178.     register object_t    **ss;
  179.     register object_t    **ws;    /* Wanted position. */
  180.  
  181.     if (*(ss = find_set_slot(s, k)) == NULL)
  182.     return 0;
  183.     --s->s_nels;
  184.     sl = ss;
  185.     /*
  186.      * Scan "forward" bubbling up entries which would rather be at our
  187.      * current empty slot.
  188.      */
  189.     for (;;)
  190.     {
  191.     if (--sl < s->s_slots)
  192.         sl = s->s_slots + s->s_nslots - 1;
  193.     if (*sl == NULL)
  194.         break;
  195.     ws = &s->s_slots[(unsigned long)*sl % s->s_nslots];
  196.     if
  197.     (
  198.         (sl < ss && (ws >= ss || ws < sl))
  199.         ||
  200.         (sl > ss && (ws >= ss && ws < sl))
  201.     )
  202.     {
  203.         /*
  204.          * The value at sl, which really wants to be at ws, should go
  205.          * into the current empty slot (ss).  Copy it to there and update
  206.          * ss to be here (which now becomes empty).
  207.          */
  208.         *ss = *sl;
  209.         ss = sl;
  210.     }
  211.     }
  212.     *ss = NULL;
  213.     return 0;
  214. }
  215.  
  216. /*
  217.  * Add or delete the key k from the set based on the value of v.
  218.  */
  219. STATIC int
  220. assign_set(s, k, v)
  221. set_t            *s;
  222. register object_t    *k;
  223. register object_t    *v;
  224. {
  225.     register object_t    **e;
  226.  
  227.     if (objof(s)->o_flags & O_ATOM)
  228.     {
  229.     error = "attempt to modify an atomic set";
  230.     return 1;
  231.     }
  232.     if (isfalse(v))
  233.     {
  234.     return unassign_set(s, k);
  235.     }
  236.     else
  237.     {
  238.     e = find_set_slot(s, k);
  239.     if (*e == NULL)
  240.     {
  241.         if (++s->s_nels >= s->s_nslots - s->s_nslots / 5)
  242.         {
  243.         /*
  244.          * This set has become 80% full.  Grow it.
  245.          */
  246.         if (grow_set(s))
  247.             return 1;
  248.         e = find_set_slot(s, k);
  249.         }
  250.         *e = k;
  251.     }
  252.     }
  253.  
  254.     return 0;
  255. }
  256.  
  257. STATIC object_t *
  258. fetch_set(s, k)
  259. set_t            *s;
  260. register object_t    *k;
  261. {
  262.     return *find_set_slot(s, k) == NULL ? objof(&o_null) : objof(o_one);
  263. }
  264.  
  265. type_t    set_type =
  266. {
  267.     mark_set,
  268.     free_set,
  269.     hash_set,
  270.     cmp_set,
  271.     copy_set,
  272.     assign_set,
  273.     fetch_set,
  274.     "set"
  275. };
  276.  
  277. /*
  278.  * Return 1 if a is a subset of b, else 0.
  279.  */
  280. int
  281. set_issubset(a, b) /* a is a subset of b */
  282. set_t *a;
  283. set_t *b;
  284. {
  285.     register object_t    **sl;
  286.     register int    i;
  287.     
  288.     for (sl = a->s_slots, i = 0; i < a->s_nslots; ++i, ++sl)
  289.     {
  290.     if (*sl == NULL)
  291.         continue;
  292.         if (*find_set_slot(b, *sl) == NULL)
  293.         return 0;
  294.     }
  295.     return 1;
  296. }
  297.  
  298. /*
  299.  * Return 1 if a is a proper subset of b, else 0. That is, is a subset
  300.  * and not equal.
  301.  */
  302. int
  303. set_ispropersubset(a, b) /* a is a proper subset of b */
  304. set_t *a;
  305. set_t *b;
  306. {
  307.     return a->s_nels < b->s_nels && set_issubset(a, b);
  308. }
  309.